As integrated circuit device dimensions continue to shrink, it is becoming increasingly difficult to form circuit features and other layout shapes using conventional single pattern lithography processes. The recent development of extreme ultra violet (EUV) single pattern lithography processes will potentially allow the accurate patterning of ultra deep submicron shapes, but there remain significant difficulties in the practical implementation of these EUV processes.
An alternative approach to extending the range of conventional lithography processes is known as double patterning technology (DPT). The DPT approach generally involves decomposing the layout of a given layer of an integrated circuit design into two separate sub-layers each of which is associated with different pattern mask. The two pattern masks are separately exposed but collectively form the desired features or other shapes of the overall layout.
The decomposition process may separate certain continuous shapes into segments, such that segments that are within a specified minimum distance of one another are placed in different sub-layers. Two connected segments of the layout printed using the separate masks overlie one another at a point referred to as a “stitch.” This is the point where the two segments printed in different masks overlay to form the original continuous shape. Thus, the DPT approach requires accurate overlay control between the segments in the two masks. Such overlay control is particularly challenging in view of rounding errors that typically arise at the ends of actual printed shapes at the stitch locations due to the lithography process, and the difficulty of the overlay control increases with the number of stitches. Therefore, it is very important to reduce the number of stitches in a decomposition.
Known techniques for reducing the number of stitches in a decomposition typically utilize either an Integer Linear Programming (ILP) approach or a heuristics approach. Examples of the ILP approach include techniques described in A. Kahng et al., “Layout decomposition for double patterning lithography,” ICCAD 08, pp 465-472, 2008, and K. Yuan et al., “Double patterning layout decomposition for simultaneous conflict and stitch minimization,” ISPD 09, pp 107-114, 2009. Examples of the heuristics approach include the techniques disclosed in J. S. Yang et al., “A new graph-theoretic, multi-objective layout decomposition framework for double patterning lithography,” ASPDAC 10, pp 637-644, 2010.
However, obtaining optimal decompositions using the ILP approaches is unduly complex and time-consuming, and therefore such approaches are generally not suitable for use with layouts that include very large numbers of circuit features and other shapes. The heuristics approaches are also problematic in that such approaches tend to result in sub-optimal decompositions, that is, decompositions in which the number of stitches is not minimized.
Accordingly, a need exists for improved layout decomposition techniques which can reduce the number of stitches in an optimal manner and yet exhibit significantly reduced complexity relative to ILP approaches.